Conventional cryptographic algorithms allow two users, who already possess a common secret key, to exchange private messages even when communicating over a public network. Such systems possess very fast software implementations, inexpensive and fast hardware implementations, and, most importantly, are very secure. In fact, their security simply relies on one-way functions: functions f that are easy to evaluate but hard to invert, that is, for which it is hard, given a generic value z=f(x), to find any value y such that f(y)=z.
Despite these main advantages, conventional cryptosystems, however, are not very useful. Prior exchange of a common secret key (e.g., by physically meeting in a secure location) with every person with whom one wants to talk to in private is, to say the least, cumbersome in most scenarios.
To overcome this difficulty, several methods have been developed to allow two people to agree on a common secret keys in a convenient manner. Unfortunately, however, until now all publicly known protocols for this task are either based on the assumed computational difficulty of a given number theoretical problem (as in the Diffie-Hellman algorithm and the RSA algorithm), or they rely on a non-realistic amount of trust.
In the case of RSA, the encryption function f(x) typically is x.sup.e mod n, where n is a publicly-known product of two large prime integers P.sub.1 and P.sub.2 (known only to the user who publishes n and e), and e is a publicly known exponent (relatively prime with P.sub.1 and P.sub.2). In the RSA system, if a user X publishes two values e and n as above, then user Y can select a secret key k in an arbitrary manner and communicate it privately to X, by looking up X's publicized values, computing k'=k.sup.e mod n, and sending k' to X over a public network. If computing e-roots modulo a composite integer whose factorization is not known is a virtually impossible computational problem, then only user X will be capable of retrieving k from k'; in fact, only X knows n's factorization (i.e., P.sub.1 and p.sub.2), and this knowledge makes extracting e roots feasible, though not trivial.
In the case of the Diffie-Hellman scheme, two users X and Y, respectively possessing public keys g.sup.x mod p and g.sup.y mod p (where p is a prime integer and g a generator mod p), and corresponding secret keys x and y, agree on a common secret key g.sup.xy mod p as follows. User X computes a value g.sup.yx =(g.sup.y).sup.x mod p (which he can do because he knows Y's public key and his own secret key); user Y computes g.sup.xy =(g.sup.x).sup.y mod p (which she can do because she knows X's public key and her own secret key. Since multiplication is commutative, g.sup.yx =g.sup.xy mod p is the desired common secret key.
In both the RSA and the Diffie-Hellman algorithms, however, the operations involved for secret-key exchange are quite time-consuming in software (computations of the type a.sup.b mod c are not-trivial whenever these values are large), or they require complex and expensive VLSI chips for fast modular exponentiation. Thus, building large-scale systems for secret-key exchange using such techniques would require a great financial investment.
More importantly, the assumptions necessary for the above secret-key exchange schemes to be secure are very rigid. In the case of RSA, secret-key exchange is performed by means of an encryption function, f(x)=x.sup.e mod n, that should not simply be one-way, but should also possess a secret (i.e., the factorization of n) knowing which inverting f (i.e., computing x from f(x)) should become possible rather than practically impossible. While it is widely believed that one-way functions exist, fewer researchers believe that one-way functions possess this additional property. Similarly, in the case of Diffie-Hellman, g.sup.x mod p not only needs to be one-way, but it should also possess additional algebraic and multiplicativity properties. Again, few people believe that one-way functions satisfying such additional algebraic constraints exist. Indeed, continuous algorithmic advances are made that make factoring integers and solving the discrete logarithm problem easier.
Therefore, conventional cryptography does not provide any efficient means to achieve secret-key exchange.
Other algebraic schemes for secret-key exchange have been devised by Blom and by Blundo et al., but these schemes rely upon an unrealistic amount of trust. In fact, not only do these schemes require a central authority that knows all the individual secret keys of the users, but also that essentially that all of the users in a large system are trustworthy. For instance, in Blom's case, as described in an article titled "An Optimal Class of Symmetric Key Generation Systems," Advances in Cryptology: Proceedings of Eurocrypt 84, Lecture Notes in Computer Science, Vol. 209, Springer-Verlag, Berlin, 1987, pp. 335-338, a trusted authority prepares and distributes keys to a group of n users. If each user key is B .cndot. R-bit long, the authority can compute from his own key (without interaction) a k-bit long common secret key for every other user in the system. All these keys will remain secret, unless k of the users collaborate and reveal to each other the keys in their possession. If this happens, they can compute the secret keys of every other user in the system.
Moreover, with such schemes few bad users may achieve the same results of many more bad users by forcing good ones to surrender their own secret keys. While in other schemes forcing some users to reveal their own keys may allow an enemy to understand at most the communications of those users (who will be aware of having lost privacy), in these algebraic schemes an enemy who has forced a sufficient number of users to reveal their own secret keys will understand the communications of all users, which is obviously untenable.
In sum, therefore, prior art techniques are inadequate for setting up truly viable secret-key exchange systems, especially where such systems are designed for large-scale use where the number of potentially dishonest users is enormous and there is no single individual that all users would trust to know their keys.